#include "evenOddMergeSort.h"

// ------------------- CONSTRUCTORS AND DESTRUCTORS ----------------------
EvenOddMergeSort::EvenOddMergeSort(){

}

EvenOddMergeSort::~EvenOddMergeSort(){

}

//-------------------- PUBLIC METHODS ------------------------------------

// Sort items with EvenOddMergeSort algorithm
void EvenOddMergeSort::sort(Array * a){
    this->a = a->getArray();
    this->sortImpl(0, a->getCnt());
    this->a = NULL;
}

void EvenOddMergeSort::sortImpl(int ind, int cnt)
{
    if (cnt <= 1)
        return;
    int half = cnt / 2;
    this->sortImpl(ind, half);
    this->sortImpl(ind + half, cnt - half);
    this->merge(ind, 1, cnt);
}

void EvenOddMergeSort::merge(int ind, int dist, int cnt)
{
    int m = dist * 2;
    if (m < cnt)
    {
        this->merge(ind, m, cnt);
        this->merge(ind + dist, m, cnt);
        for (int i = ind + dist; i + dist < ind + cnt; i += m)
            compare(i, i + dist);
    } else
    {
        this->compare(ind, ind + dist);
    }
}

void EvenOddMergeSort::compare(int i, int j)
{
    if (a[i] > a[j])
    {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}
